package com.klun.project.common.constans.leetcode;

//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
// 返回满足题意的二叉搜索树的种数。
//
// 示例 1：
//输入：n = 3
//输出：5
//
// 示例 2：
//输入：n = 1
//输出：1
//
// 提示：
// 1 <= n <= 19
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树
// 👍 1966 👎 0


public class Solution96 {

	// G(n) = 笛卡尔积求和 i:从1到n  G(i-1) * G(n-i)
	// f(i,n) = G(i-1) * G(n-i)
	// G(n) = f(i,n) + f(i-1,n) + .... + f(0,n)  1<= i <=n
	// f(i) = f(i-1) + f(i-2) + ..... + f(0) ;
	public int numTrees(int n) {
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i < n + 1; i++) {
			for (int j = 1; j <= i; j++) {
				dp[i] += dp[j - 1] * dp[i - j];
			}
		}
		return dp[n];
	}

	public static void main(String[] args) {
		Solution96 solution = new Solution96();
		System.out.println(solution.numTrees(3));
	}

}
